#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string>
#include <math.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <memory>  //智能指针
#include <utility> //类pair的声明
#include <unordered_map>
#include <fstream>
#include <sstream>
#include <thread>
#include <mutex>
#pragma once
#include "ThreadCache.hpp"
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void* ptr=virtualAlloc(0,kpage<<13,MEM_COMMIT | MEM_RESERVE,PAGE_READWRI);
    #else
    #endif
    return ptr;
}
inline static void* SystemFree(void* ptr)
{
    delete ptr;
}
static const size_t MAX_BYTES = 256 * 1024; // 最大字节数为256KB
static const size_t NFREELIST = 208;        // 桶的数量
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;
static void *&NextObj(void *obj)
{
    return *(void **)obj;
}
class FreeList
{
public:
    void Push(void *obj)
    {
        assert(obj);
        NextObj(obj) = _freelist;
        _freelist = obj;
        ++_size;
    }
    void *Pop()
    {
        assert(_freelist);
        void *obj = _freelist;
        _freelist = NextObj(obj);
        --_size;
        return obj;
    }
    bool Empty()
    {
        if (_freelist == nullptr)
            return true;
        else
            return false;
    }
    void PushRange(void* start, void* end,size_t n)
	{
		//	一连串空间存储
		NextObj(end) = _freelist;
		_freelist = start;
        _size+=n;
	}
    void PopRange(void*&start,void*&end,size_t n)
    {
        assert(n>=_size);
        start=_freelist;
        end=start;
        for(int i=0;i<n-1;++i)
        {
            end=NextObj(end);
        }
        _freelist=NextObj(end);
        NextObj(end)=nullptr;
        _size-=n;
    }
    size_t Size()
    {
        return _size;
    }
    size_t& MaxSize()
    {
        return _maxSize;
    }
private:
    void *_freelist = nullptr;
    size_t _maxSize=1;  //表示向CentralCache要空间数量的上限
    size_t _size=0;
};
class SizeClass
{
public:
    // 计算一次向系统获取几个页
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);
        size_t npage = num * size;

        npage >>= PAGE_SHIFT;   //npage表示要获取的第几页page
        if (npage == 0)
            npage = 1;
        return npage;
    }
    
    static size_t NumMoveSize(size_t size)
    {
        assert(size>0);
        int num=MAX_BYTES/size;
        if(num<2)
        num=2;
        if(num>512)
        num=512;
        
        return num;
    }
    static inline size_t _Roundup(size_t size, size_t alignNum) 
    {
        if (size % alignNum == 0)
        {
            return (size / alignNum - 1) * alignNum;
        }
        else
        {
            return (size / alignNum) * alignNum;
        }
    }
    static inline size_t Roundup(size_t size)  //算出桶的大小（即size的对齐数）
    {
        if (size <= 128)
        {
            return _Roundup(size, 8);
        }
        else if (size <= 1024)
        {
            return _Roundup(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            return _Roundup(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            return _Roundup(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            return _Roundup(size, 8 * 1024);
        }
        else
        {
            return _Roundup(size, 1<<PAGE_SHIFT);
        }
    }
    static size_t Index(size_t size)
    {
        int group[5] = {16, 56, 56, 56, 24};
        if (size <= 128)
        {
            return _Index(size, 8);
        }
        else if (size <= 1024)
        {
            return _Index(size - 128, 16) + group[0];
        }
        else if (size <= 8 * 1024)
        {
            return _Index(size - 1024, 128) + group[0] + group[1];
        }
        else if (size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 1024) + group[0] + group[1] + group[2];
        }
        else if (size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 8 * 1024) + group[0] + group[1] + group[2];
            +group[3];
        }
        else
        {
            assert(size <= 256 * 1024);
            return -1;
        }
    }
    static size_t _Index(size_t size, size_t alignNum)
    {
        if (size % alignNum == 0)
        {
            return size / alignNum - 1;
        }
        else
        {
            return size / alignNum;
        }
    }
};
struct Span
{
    PAGE_ID _pageId = 0;  //大块内存起始页的页号，可以通过页号找到起始地址，页可以通过起始地址找到对应页号

    Span *_next = nullptr;
    Span *_prev = nullptr;
    size_t _n;              //标识第几页
    size_t _useCount = 0;   //切好的小块内存，被分配给thread cache的计数
    void *_freeList = nullptr;   // 切好的小块内存的自由链表
    bool _isUse=false;
};

class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }
    Span *Begin()
    {
        return _head->_next;
    }
    Span *End()
    {
        return _head;
    }
    Span* PopFront()
    {
        assert(_head->_next);
        Span* front=_head->_next;
        Erase(front);
        return front;
    }
    void PushFront(Span* newSpan)
    {
        Insert(Begin(),newSpan);
    }
    void Insert(Span *pos, Span *newSpan)   //在pos前插入一快Span
    {
        assert(pos);
        assert(newSpan);
        Span* prev=pos->_prev;
        prev->_next=newSpan;
        newSpan->_prev=prev;
        newSpan->_next=pos;
        pos->_prev=newSpan;
    }
    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos!=_head);
        Span*prev=pos->_prev;
        Span*next=pos->_next;
        prev->_next=next;
        next->_prev=prev;
    }
    bool Empty()
    {
        return _head->_next==nullptr;
    }
public:
    mutex _mutex;
private:
    Span *_head;
    
};